package Year22_Month05.day23;

import java.util.Arrays;

public class 希尔排序 {
    //希尔排序
    public static void shell(int[] arr){
        int gap = arr.length;
        //首先要明白，当size == 1或者小于1的时候就没有必要进行排序了，此时已经是有序的了。
        while(gap > 1){
            //这里间隔选取还是要注意一下的
            gap = gap / 3 + 1;
            //以下代码就是插入排序基础上稍稍改造了一下
            for(int i = gap;i < arr.length;i++){
                int key = arr[i];
                int end = i - gap;
                while(end >= 0 && arr[end] > key){
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                arr[end + gap] = key;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        shell(arr);
        System.out.println(Arrays.toString(arr));
    }
}
